package leetcode.editor.cn.dp;

//给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。 
//
// 
//
// 示例 1: 
//输入: 
//
// "bbbab"
// 
//
// 输出: 
//
// 4
// 
//
// 一个可能的最长回文子序列为 "bbbb"。 
//
// 示例 2: 
//输入: 
//
// "cbbd"
// 
//
// 输出: 
//
// 2
// 
//
// 一个可能的最长回文子序列为 "bb"。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 只包含小写英文字母 
// 
// Related Topics 动态规划 
// 👍 433 👎 0

class LongestPalindromicSubsequence {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubsequence().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * @Time:
         * @Space:
         * @Author: 赖锦帆
         * @Date: 2021-04-22 11:47
         * 子序列问题三种：
         * 1.一维：dp[i]以str[i]结尾的目标子序列的长度为dp[i]
         * 2.二维：A涉及两个字符串/数组:dp[i][j]:
         * 在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]
         * 二维：B涉及一个字符串/数组:
         * 在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]
         *
         * 本题属于2.B情况
         */
        public int longestPalindromeSubseq(String s) {
            int[][] dp = new int[s.length()][s.length()];
            if (s==null||s.equals(""))
                return 0;
            for (int i = 0; i < dp.length; i++) {
                dp[i][i] = 1;
            }
            for (int i = dp.length - 1; i >= 0; i--) {
                for (int j = i + 1; j < s.length(); j++) {
                    if (s.charAt(i)==s.charAt(j))
                        dp[i][j] = dp[i+1][j-1] + 2;
                    else dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
            return dp[0][dp.length-1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
